#include"DynamicArray.h"
#include<cmath>

namespace DARRAY
{
    DynamicArray::DynamicArray()
    {
        size = 0;
        capacity = 10;
        array = new ElementType[capacity];
        Free = nullptr;
        CopyData = nullptr;   //
        Compare = nullptr;
        Greater = nullptr;
        Print = nullptr;
    }

    DynamicArray::DynamicArray(const DynamicArray & a)
    {
        size = a.size;
        capacity = a.capacity;
        array = new ElementType[capacity];

        CopyData = a.CopyData;   
        Free = a.Free;
        Compare = a.Compare;
        Greater = a.Greater;
        Print = a.Print;

        for(size_t i = 0; i < size; i++)//这里i的类型要是size_t,防止溢出
        {
            if(Free != nullptr)
                array[i] = CopyData(a.array[i]);
            else
                array[i] = a.array[i];
        }
        
    }

    DynamicArray& DynamicArray::operator=(const DynamicArray & a)
    {
        delete []array;
        size = a.size;
        capacity = a.capacity;
        array = new ElementType[capacity];

        CopyData = a.CopyData;   
        Free = a.Free;
        Compare = a.Compare;
        Greater = a.Greater;
        Print = a.Print;

        for(size_t i = 0; i < size; i++)
        {
            if(Free != nullptr)
                array[i] = CopyData(a.array[i]);
            else
                array[i] = a.array[i];
        }

        return *this;
    }

    DynamicArray::~DynamicArray()
    {
        if(Free)
        {
            for(size_t i = 0; i < size; i++)
            {
                Free(array[i]);
            }
        }
        delete []array;
    }

    void DynamicArray::InsertTail(const ElementType &element)//时间复杂度——不扩容:O(1)扩容:O(n)
    {
        if(size == capacity)//数组满
        {
            ReSize(capacity *= 2);
        }
        if(Free == nullptr)
            array[size++] = element;
        else
            array[size++] = CopyData(element);
    }

    void DynamicArray::InsertHead(const ElementType &element)//时间复杂度 O(n)
    {
        if(size == capacity)
        {
            ReSize(capacity *= 2);
        }
        for(size_t i = size; i > 0; i--)
        {
            array[i] = array[i - 1]; 
        }
        if(Free == nullptr)
            array[0] = element;
        else
            array[0] = CopyData(element);
        size++;
    }

    void DynamicArray::InsertIndex(const ElementType & element, size_t index)//时间复杂度 O(n)
    {
        if(index > size)
        {
            std::cout << "插入位置非法\n";
            return ;
        }
        if(size == capacity)
        {
            ReSize(capacity *= 2);
        }
        for(size_t i = size; i > index; i--)
        {
            array[i] = array[i - 1]; 
        }
        if(Free == nullptr)
            array[index] = element;
        else
            array[index] = CopyData(element);
        size++;
    }

    void DynamicArray::RemoveByIndex(size_t index)//时间复杂度O(n)
    {
        if(index >= size)
        {
            std::cout << "删除位置非法\n";
            return;
        }
        if(Free != nullptr)
            Free(array[index]);
        for(size_t i = index; i < size - 1; i++)
        {
            array[i] = array[i + 1];
        }
        size--;
    }

    void DynamicArray::RemoveByElement(const ElementType &element)  //O(n^2)
    {
        for(size_t i = 0; i < size; i++)
        {
            if(Compare(array[i],element))     //array[i] == element
            {
                RemoveByIndex(i);
                i--;//不加入这个会导致无法删除相邻数据
            }
        }    
    }

    ElementType* DynamicArray::FindByIndex(size_t index)//O(1)
    {
        if(index >= size)
        {
            return nullptr;
        }
        return &array[index];
    }

    DynamicArray DynamicArray::FindByElement(const ElementType &element)//O(n)
    {
        DynamicArray result;
        for(size_t i = 0; i < size; i++)
        {
            if(Compare(array[i],element))   //array[i] == element
            {
                
                result.InsertTail(array[i]);
            }
        }
        return result;
    }

    void DynamicArray::UpdataByIndex(size_t index, const ElementType &newValue) //O(1)
    {
        if(index >= size)
        {
            std::cout << "修改位置非法!\n";
            return ;
        }
        if(Free == nullptr)
            array[index] = newValue;
        else
        {
            Free(array[index]);
            array[index] = CopyData(newValue);
        }
    }

    void DynamicArray::UpdataByElement(const ElementType &oldValue, const ElementType &newValue)    //O(n)
    {
        for(size_t i = 0; i < size; i++)
        {
            if(Compare(array[i],oldValue))    //array[i] == oldValue
            {
                if(Free == nullptr)
                    array[i] = newValue;
                else
                {
                    Free(array[i]);
                    array[i] = CopyData(newValue);
                }
            }
        }
    }

    ElementType &DynamicArray::operator[](int index)//无法判断越界问题,只有指针才可以判断非法值
    {
        return array[index];
    }

    void DynamicArray::Sort()
    {
        FastSort(0,size - 1,0,2 * log2(size));
    }

    void DynamicArray::Duplicate()  //O(n)
    {
        for(size_t i = 1; i < size; i++)
        {
            if(Compare(array[i],array[i - 1]))    //array[i] == array[i - 1]
            {   
                RemoveByIndex(i);
                i--;//很重要:一旦修改数组的元素位置，就要考虑i一次越过两格的可能性
            }
        }
    }

    DynamicArray DynamicArray::Merge(const DynamicArray &a)    //O(n)
    {
        DynamicArray result;
        result.Free = a.Free;
        result.CopyData = a.CopyData;
        size_t first = 0;//当前数组
        size_t second = 0;//传进来的数组
        while(first < this->size && second < a.size)
        {
            if(Greater(array[first],a.array[second]) == false)      //array[first] < a.array[second]
                result.InsertTail(array[first++]);
            else
                result.InsertTail(a.array[second++]);
        }
        while(first < this->size)
            result.InsertTail(array[first++]);
        while(second < a.size)
            result.InsertTail(a.array[second++]);
        return result;
    }

    DynamicArray DynamicArray::FdIntrSctn(const DynamicArray & a)   //O(n)
    {
        DynamicArray result;
        result.Free = a.Free;
        result.CopyData = a.CopyData;
        size_t first = 0;
        size_t second = 0;
        while(first < this->size && second < a.size)
        {
            if(Compare(array[first],a.array[second]))     //array[first] == a.array[second]
            {
                result.InsertTail(array[first++]);
                second++;
            }
            else if(Greater(array[first],a.array[second]) == false)     //array[first] < a.array[second]
            {
                first++;
            }
            else if(Greater(array[first],a.array[second]))     //array[first] > a.array[second]
            {
                second++;
            }
        } 
        return result;   
    }

    DynamicArray DynamicArray::FdUnionSet(const DynamicArray &a)    //O(n)
    {
        DynamicArray result;
        result.Free = a.Free;
        result.CopyData = a.CopyData;
        size_t first = 0;
        size_t second = 0;
        while(first < this->size && second < a.size)
        {
            if(Compare(array[first],a.array[second]))     //array[first] == a.array[second]
            {
                result.InsertTail(array[first++]);
                second++;
            }
            else if(Greater(array[first],a.array[second]) == false)     //array[first] < a.array[second]
            {
                result.InsertTail(array[first++]);
            }
            else if(Greater(array[first],a.array[second]))      //array[first] > a.array[second]
            {
                result.InsertTail(a.array[second++]);
            }
        }
        while(first < this->size)
            result.InsertTail(array[first++]);
        while(second < a.size)
            result.InsertTail(a.array[second++]); 
        return result;       
    }

    DynamicArray DynamicArray::FindDifference(const DynamicArray &a)    //O(n)
    {
        DynamicArray result;
        result.Free = a.Free;
        result.CopyData = a.CopyData;
        size_t first = 0;
        size_t second = 0;
        while(first < size && second < a.size)
        {
            if(Compare(array[first],a.array[second]))     
            {
                first++;
                second++;
            }
            else if(Greater(array[first],a.array[second]) == false)
            {
                result.InsertTail(array[first++]);
            }
            else if(Greater(array[first],a.array[second]))
            {
                result.InsertTail(a.array[second++]);
            }
        }
        while(first < this->size)
            result.InsertTail(array[first++]);
        while(second < a.size)
            result.InsertTail(a.array[second++]); 
        return result; 
    }

    bool DynamicArray::operator==(const DynamicArray &a)    //O(n)
    {
        if(size != a.size)
            return false;
        size_t first = 0;
        size_t second = 0;
        while(first < size && second < a.size)
        {
            if(Compare(array[first++],a.array[second++]) == false)     //array[first++] != a.array[second++]
            {
                return false;
            }
        }
        return true;
    }

    size_t DynamicArray::BinarySearch(const ElementType &element)
    {
        size_t left = 0;
        size_t right = size - 1;
        while(left <= right)
        {
            size_t mid = left + (right - left) / 2;
            if(Compare(array[mid],element))   //array[mid] == element
                return mid;
            else if(Greater(array[mid],element))       //array[mid] > element
            {
                if(mid == 0)
                    return ULONG_MAX;
                right = mid - 1;
            }
            else if(Greater(array[mid],element) == false)   ////array[mid] < element
            {
                left = mid + 1;
            }
        }
        return ULONG_MAX;
    }

    bool DynamicArray::Contains(const DynamicArray &a)  //O(n)
    {
        //DynamicArray s = FdIntrSctn(a);
        //return s == a;
        size_t j = 0;
        for(size_t i = 0; i < size && j < a.size; i++)
        {
            if(Compare(array[i],a.array[j]))      //array[i] == a.array[j]
                j++;
        }
        return j == a.size;

    }

    bool DynamicArray::ContnsContains(const DynamicArray &a)
    {
        for(size_t i = 0; i <= size - a.size; i++)
        {
            if(SubSquence(i,a.size) == a)
            {
                return true;
            }
        }
        return false;
    }

    DynamicArray DynamicArray::SubSquence(size_t index, size_t len)
    {
        DynamicArray result;
        result.Compare = Compare;
        if(index + len > size)
        {
            return result;
        }
        for(size_t i = 0; i < len; i++)
        {
            result.InsertTail(array[index + i]);
        }
        return result;
    }

    void DynamicArray::show()
    {
        for(size_t i = 0; i < size; i++)
        {
            Print(array[i]);
        }
    }

    size_t DynamicArray::partition(size_t start, size_t end)
    {
        size_t left = start;
        size_t right = end;
        ElementType temp = array[start];
        while(left < right)
        {
            while(Greater(array[right],temp) && left < right)      //array[right] > temp
            {
                right--;
            }
            if(left < right)
                array[left++] = array[right];

            while(Greater(array[left],temp) == false && left < right)       //array[left] < temp
            {
                left++;
            }
            if(left < right)
                array[right--] = array[left];            
        }
        array[left] = temp;

        return left;
    }

    void DynamicArray::FastSort(size_t start, size_t end,size_t CurDepth,size_t MaxDepth)//递归深度过深，导致栈空间不足的情况——爆栈
    {
        if(start >= end)
            return ;

        //如果没有达到最大的递归深度
        if(CurDepth < MaxDepth)
        {
            size_t par = partition(start,end);//将数列分组
            if(par != 0)//防止数据溢出
                FastSort(start,par - 1,CurDepth + 1,MaxDepth);
            FastSort(par + 1,end,CurDepth + 1,MaxDepth);
        }
        //超过最大深度，使用插入排序
        else
        {
            InsertSort(start,end);
        }

    }

    void DynamicArray::InsertSort(size_t start, size_t end)
    {
        for(size_t i = start + 1; i <= end; i++)
        {
            size_t j = i;
            ElementType tmp = array[i];
            for(;j > start; j--)
            {
                if(Greater(array[j - 1],tmp))      //array[j - 1] > tmp
                    array[j] = array[j - 1];
                else
                    break;
            }
            array[j] = tmp;
        }
    }

    void DynamicArray::ReSize(size_t capacity)
    {
        this->capacity = capacity;
        size = size > capacity ? capacity : size;
        ElementType *newPtr = new ElementType[capacity];
        for(size_t i = 0; i < size; i++)
        {
            newPtr[i] = array[i];
        }
        delete []array;
        array = newPtr;
    }
}